package th.retrofit.lib;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 组合总和
 * https://leetcode-cn.com/problems/combination-sum-ii/
 */
final class Solution40 {

    /**
     * @param candidates 一个无重复元素的正整数数组candidates
     * @param target 一个正整数target
     * @return candidates中所有可以使数字和为目标数target的唯一组合, 每个数字仅能使用一次
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> results = new LinkedList<>();
        List<Integer> combine = new LinkedList<>();
        dfs(candidates, target, results, combine, 0);
        return results;
    }

    private void dfs(int[] candidate, int target, List<List<Integer>> results,
                     List<Integer> combine, int index) {
        if (target < 0) return;
        if (target == 0) {
            results.add(new LinkedList<>(combine));
            return;
        }
        for (int i = index; i < candidate.length; i++) {

            //横向去重
            if (i - 1 >= index && candidate[i] == candidate[i - 1]) {
                continue;
            }
            combine.add(candidate[i]);
            dfs(candidate, target - candidate[i], results, combine, i + 1);
            combine.remove(combine.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] num = new int[]{10,1,2,7,6,1,5};
        new Solution40().combinationSum(num, 8).forEach(it -> {
            it.forEach(System.out::print);
            System.out.println();
        });
    }

}
